package s9_树.tree5_二叉排序树;

import s6_排序算法.BaseSort;

/**
 * <code>{@link BinarySortTree}</code>
 * <p>
 * description: BinarySortTree
 * <p>
 *
 * @author 西瓜瓜 on 2022/2/26 9:33
 *
 * 二叉排序树（BST）：对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点值小，右子节点的值比当前节点的值大
 * 如果有相同的节点值，可以将该节点放在左子节点或右子节点
 *
 */
public class BinarySortTree extends BaseSort {

    private BinarySortNode root;

    public void add(BinarySortNode node) {
        if(root == null){
            root = node;
            return;
        }

        root.add(node);
    }

    public void infixOrder() {
        if(root != null) {
            root.infixOrder();
        }
    }

    public BinarySortNode search(int value) {
        if(root != null) {
            return root.search(value);
        }
        return null;
    }

    public BinarySortNode searchParent(int value) {
        if(root != null) {
            return root.searchParent(value);
        }
        return null;
    }

    public void delNode(int val) {
        if(root == null) return;

        BinarySortNode targetNode = search(val);
        if(targetNode == null) return;

        if(root.leftNode == null && root.rightNode == null) {
            // 说明只有根节点
            root = null;
            return;
        }

        BinarySortNode parentNode = searchParent(val);
        // 说明是叶子节点
        if(targetNode.leftNode == null && targetNode.rightNode == null) {
            if(parentNode.leftNode != null && parentNode.leftNode.value == val) {
                parentNode.leftNode = null;
                return;
            }
            if(parentNode.rightNode != null && parentNode.rightNode.value == val) {
                parentNode.rightNode = null;
                return;
            }
        }

        // 说明待删除节点还有全子树
        if(targetNode.leftNode != null && targetNode.rightNode != null) {
            targetNode.value = delRightTreeMin(targetNode.rightNode);
            return;
        }

        // 说明待删除节点还有左子树
        if(targetNode.leftNode != null) {
            if(parentNode == null) {
                root = targetNode.leftNode;
                return;
            }

            if(parentNode.leftNode != null && parentNode.leftNode.value == val) {
                parentNode.leftNode = targetNode.leftNode;
                return;
            }
            if(parentNode.rightNode != null && parentNode.rightNode.value == val) {
                parentNode.rightNode = targetNode.leftNode;
                return;
            }

        }

        // 说明待删除节点还有右子树
        if(targetNode.rightNode != null) {
            if(parentNode == null) {
                root = targetNode.rightNode;
                return;
            }

            if(parentNode.leftNode != null && parentNode.leftNode.value == val) {
                parentNode.leftNode = targetNode.rightNode;
                return;
            }
            if(parentNode.rightNode != null && parentNode.rightNode.value == val) {
                parentNode.rightNode = targetNode.rightNode;
            }

        }
    }

    public int delRightTreeMin(BinarySortNode node) {
        BinarySortNode temp = node;

        // 循环左节点找到最小值
        while(temp.leftNode != null) {
            temp = temp.leftNode;
        }
        // 这时temp指向最小节点
        delNode(temp.value);
        return temp.value;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{7,3,10,12,5,1,9};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int value : arr) {
            binarySortTree.add(new BinarySortNode(value));
        }

        // 二叉排序树中序遍历
        binarySortTree.infixOrder();

        binarySortTree.delNode(7);
        System.out.println("!!!!!!!!!!!!!!!!!!!!!!!!!!");

        binarySortTree.infixOrder();



    }

    @Override
    public void asc(int[] arr) {
        System.out.println("BinarySortTree-------------------------------");
        long s = System.currentTimeMillis();

        BinarySortTree binarySortTree = new BinarySortTree();
        for (int value : arr) {
            binarySortTree.add(new BinarySortNode(value));
        }

        long e = System.currentTimeMillis();
        System.out.println("BinarySortTree: " + (e-s) + "ms");

    }
}




class BinarySortNode {
    int value;

    BinarySortNode leftNode;
    BinarySortNode rightNode;

    public BinarySortNode(int value) {
        this.value = value;
    }

    public void add(BinarySortNode node) {
        if(node == null) return;

        // 待添加的节点值小于当前节点值
        if(node.value < this.value) {
            if(this.leftNode == null) {
                // 当前节点的左子树为空，则挂在到当前节点的左子节点
                this.leftNode = node;
            } else {
                // 递归向左子树添加
                this.leftNode.add(node);
            }
        } else {
            if(this.rightNode == null) {
                // 当前节点的右子树为空，则挂在到当前节点的右子节点
                this.rightNode = node;
            } else {
                // 递归向右子树添加
                this.rightNode.add(node);
            }
        }

    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if(this.leftNode != null) {
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if (this.rightNode != null) {
            this.rightNode.infixOrder();
        }
    }

    /**
     * 查找要删除的节点
     * @param value 待删除节点的值
     * @return 返回当前节点
     */
    public BinarySortNode search(int value) {
        if(value == this.value) return this;

        if(value < this.value) {
            if(this.leftNode == null) return null;
            return this.leftNode.search(value);
        } else {
            if(this.rightNode == null) return null;
            return this.rightNode.search(value);
        }
    }

    /**
     * 查找要删除节点的父节点
     * @param value 待删除节点的值
     * @return 返回父节点
     */
    public BinarySortNode searchParent(int value) {
        if((this.leftNode != null && this.leftNode.value == value) ||
                (this.rightNode != null && this.rightNode.value == value)) {
            return this;
        }

        if(value < this.value && this.leftNode != null) {
            return this.leftNode.searchParent(value);
        }

        if(value >= this.value && this.rightNode != null) {
            return this.rightNode.searchParent(value);
        }

        return null;
    }




    @Override
    public String toString() {
        return "BinarySortNode{" +
                "value=" + value +
                '}';
    }
}
